package com.bigshen.algorithm.aLinearList.solution03CopyListwithRandomPointer;

import java.util.HashMap;
import java.util.Map;

/**
 * ### 138. Copy List with Random Pointer
 *
 * A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.
 *
 * Return a deep copy of the list.
 *
 * The Linked List is represented in the input/output as a list of n nodes. Each node is represented as a pair of [val, random_index] where:
 *
 * val: an integer representing Node.val
 * random_index: the index of the node (range from 0 to n-1) where random pointer points to, or null if it does not point to any node.
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/copy-list-with-random-pointer
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 *
 * 重点还是怎么维护 节点和克隆节点的关系；
 * 可以维护在map中，也可以维护在单向链表的next
 * 1 -> 2 -> 3 -> 4   ==>  1 -> 1' -> 2 -> 2' -> 3 -> 3' -> 4 -> 4'
 *
 */
public class Solution {

    public Node copyRandomList(Node head) {

        if (null == head) {
            return null;
        }

        // 将当前节点与clone节点的映射关系维护于Map中
        Map<Node, Node> map = new HashMap<>();
        Node tmp = head;
        while (null != tmp) {
            Node next = tmp.next;
            map.put(tmp, new Node(tmp.val));
            tmp = next;
        }

        // 绑定next和random关系
        tmp = head;
        while (null != tmp) {
            Node next = tmp.next;
            if (null != tmp.next) {
                // 指定clone节点的next
                map.get(tmp).next = map.get(tmp.next);
            }
            if (null != tmp.random) {
                // 指定clone节点的random
                map.get(tmp).random = map.get(tmp.random);
            }
            tmp = next;
        }

        return map.get(head);
    }

}


class Node {
    int val;
    Node next;
    Node random;

    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}
